Counting Principles: Factorial, Permutations, and Combinations

Fundamental Principle of Counting

Counting Possibilities

In many situations, especially in probability and combinatorics, we need to determine the total number of possible outcomes or ways an event or a sequence of events can occur. The Fundamental Principle of Counting provides a basic and intuitive way to figure out the total number of possibilities when multiple independent choices or events are involved. It serves as the bedrock upon which more sophisticated counting techniques like permutations and combinations are built.

---

The Multiplication Principle

The Fundamental Principle of Counting is most often articulated as the Multiplication Principle.

Statement of the Multiplication Principle:

If a task consists of a sequence of two events, and the first event can be performed in $m$ different ways, and for each of these $m$ ways, the second event can be performed in $n$ different ways, then the total number of different ways the entire task can be performed (i.e., the number of ways both events can occur in this specific order) is the product $m \times n$.

This principle can be readily extended to a sequence involving any finite number of events. If a task involves $k$ sequential events, and the first event can occur in $n_1$ ways, the second event can occur in $n_2$ ways (regardless of how the first event occurred), the third event can occur in $n_3$ ways (regardless of how the first two events occurred), and so on, until the $k$-th event can occur in $n_k$ ways, then the total number of ways to perform the entire task (the sequence of all $k$ events) is the product of the number of ways for each individual event:

$$ \text{Total Number of Ways} = n_1 \times n_2 \times n_3 \times \ldots \times n_k $$

---

Examples Using the Multiplication Principle

Let's apply the Multiplication Principle to solve some counting problems.

Answer:

---

Answer:

---

Answer:

---

The Addition Principle

While the Multiplication Principle deals with sequences of events, the Addition Principle applies when there are mutually exclusive choices or events. It is also considered part of the Fundamental Principle of Counting in a broader sense.

Statement of the Addition Principle:

If an event (let's call it Event A) can occur in $m$ different ways, and another event (Event B) can occur in $n$ different ways, and if these two events cannot occur at the same time (i.e., they are mutually exclusive or disjoint), then the total number of ways that *either* Event A *or* Event B can occur is the sum $m + n$.

Example: A student needs to choose one extra-curricular activity. They can choose from 3 options in sports or 4 options in music. If they must choose only one activity in total (either sports or music, not both), how many choices do they have?

Choosing a sport is one event (3 ways). Choosing a music activity is another event (4 ways). These two events are mutually exclusive because the student chooses *either* a sport *or* a music activity, but not both simultaneously. According to the Addition Principle, the total number of choices is $3 + 4 = 7$.

The Fundamental Principle of Counting, encompassing both the Multiplication and Addition Principles, forms the essential groundwork for systematically counting possibilities, which is vital in probability, permutations, and combinations.

Factorial Notation

Representing Products of Consecutive Integers

In counting problems, especially those dealing with arranging objects in a specific order (permutations), we often encounter expressions that are products of consecutive positive integers starting from 1. To simplify writing and working with such products, a special notation called factorial notation is used.

---

Definition of Factorial

The factorial of a non-negative integer $n$ is denoted by the symbol $n!$ and is read as "n factorial". For a positive integer $n$, it is defined as the product of all positive integers from 1 up to $n$.

For any positive integer $n$, the definition is:

$$ n! = n \times (n-1) \times (n-2) \times \ldots \times 3 \times 2 \times 1 $$

For example, $5! = 5 \times 4 \times 3 \times 2 \times 1$.

By mathematical convention, the factorial of zero is defined as 1. This definition is essential for formulas involving factorials to work consistently, particularly in the context of combinations and permutations.

Factorial is defined only for non-negative integers. It is not defined for negative integers or for non-integer values.

---

Examples of Factorial Calculations

Let's calculate the factorials for the first few non-negative integers:

• $0! = 1$ (by definition)
• $1! = 1$
• $2! = 2 \times 1 = 2$
• $3! = 3 \times 2 \times 1 = 6$
• $4! = 4 \times 3 \times 2 \times 1 = 24$
• $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$
• $6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720$
• $7! = 7 \times 6! = 7 \times 720 = 5040$

As you can see, factorial values grow very rapidly as $n$ increases.

---

Properties and Applications of Factorials

Factorial notation has several useful properties and appears in various mathematical areas:

1. Recursive Relation: A key property of factorials is that for any positive integer $n$, the factorial of $n$ can be expressed as the product of $n$ and the factorial of $(n-1)$.

   From the definition, $n! = n \times (n-1) \times (n-2) \times \ldots \times 2 \times 1$.

   We can group the terms $(n-1) \times (n-2) \times \ldots \times 2 \times 1$, which is the definition of $(n-1)!$.

   $n! = n \times (n-1)! \quad (\text{for } n \ge 1) $

   (Recursive Property)

   Example: $5! = 5 \times 4! = 5 \times 24 = 120$.

   This property is also consistent with the definition $0! = 1$. If we apply the property for $n=1$: $1! = 1 \times (1-1)! = 1 \times 0!$. Since we know $1! = 1$, we must have $1 = 1 \times 0!$, which implies $0! = 1$.

2. Simplifying Expressions with Factorials: The recursive property is very useful for simplifying fractions or expressions involving factorials.

   Example 1. Evaluate $\frac{8!}{6!}$.

   Answer:

   We can expand the factorials according to the definition:

   $$ \frac{8!}{6!} = \frac{8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}{6 \times 5 \times 4 \times 3 \times 2 \times 1} $$

   Alternatively, using the recursive property, we can write $8!$ as $8 \times 7 \times 6!$:

   $$ \frac{8!}{6!} = \frac{8 \times 7 \times (6!)}{6!} $$

   Now, we can cancel out the $6!$ term from the numerator and the denominator (since $6!$ is a common non-zero factor):

   $$ \frac{\cancel{6!}}{\cancel{6!}} $$

   This leaves:

   $$ = 8 \times 7 = 56 $$

   Answer: $\frac{8!}{6!} = 56$.

   Example 2. Evaluate $\frac{n!}{(n-2)!}$ for $n \ge 2$.

   Answer:

   Use the recursive property to expand $n!$ until we reach $(n-2)!$:

   $$ n! = n \times (n-1) \times (n-2) \times (n-3) \times \ldots \times 1 $$ $$ n! = n \times (n-1) \times [(n-2) \times (n-3) \times \ldots \times 1] $$ $$ n! = n \times (n-1) \times (n-2)! $$

   Now substitute this into the expression:

   $$ \frac{n!}{(n-2)!} = \frac{n \times (n-1) \times (n-2)!}{(n-2)!} $$

   Cancel out the $(n-2)!$ term:

   $$ = n(n-1) $$

   Provided $n-2 \ge 0$, i.e., $n \ge 2$.

   Answer: $\frac{n!}{(n-2)!} = n(n-1)$ for $n \ge 2$.

3. Counting Permutations and Combinations: Factorial notation is fundamental to the formulas for calculating permutations (arrangements) and combinations (selections).
4. Series Expansions: Factorials appear in the denominators of the terms in many important infinite series expansions of functions, such as the Taylor and Maclaurin series for $e^x$, $\sin x$, $\cos x$, etc.
5. Probability Theory: Factorials are used extensively in calculating probabilities in problems involving ordered or unordered selections.

Factorial notation is a crucial shorthand in combinatorics and serves as a building block for understanding concepts related to arrangements, selections, and series in algebra and beyond.

Permutations: Definition, Formula, and Types (Distinct/Identical Objects)

Arrangements of Objects

In combinatorics, we are often interested in counting the number of ways objects can be arranged or selected. A permutation specifically deals with the arrangement of objects where the order of the objects is important. If we change the order of the objects, we get a new permutation.

For example, if we have the letters A, B, and C, the possible permutations of these three letters taken all at once are ABC, ACB, BAC, BCA, CAB, and CBA. Each of these is a distinct permutation because the order of the letters is different.

---

Definition of Permutation

A permutation is a specific ordered arrangement of a set of objects. When we talk about permutations, we are interested in the number of ways to arrange a certain number of objects chosen from a larger collection, where the sequence or position of the chosen objects matters.

The number of permutations of $n$ distinct objects taken $r$ at a time refers to the number of different ordered arrangements that can be formed using $r$ objects selected from a set of $n$ unique objects. This is denoted by the symbol $P(n, r)$, $_nP_r$, or sometimes $P_r^n$.

The constraints on $n$ and $r$ are that $n$ must be a non-negative integer, and $r$ must be a non-negative integer such that $0 \le r \le n$. We can't arrange more objects than we have available.

---

Formula for Permutations of Distinct Objects

Let's derive the formula for the number of permutations of $n$ distinct objects taken $r$ at a time, denoted $P(n, r)$. This is the number of ways to fill $r$ ordered positions using objects from a set of $n$ distinct objects, without repetition of objects within the arrangement.

We can think of this as filling $r$ empty slots, one by one:

• For the first position, we have $n$ distinct objects to choose from. So there are $n$ ways to fill the first slot.
• After filling the first position, there are $n-1$ distinct objects remaining. So there are $n-1$ ways to fill the second slot.
• After filling the first two positions, there are $n-2$ distinct objects remaining. So there are $n-2$ ways to fill the third slot.
• This process continues until we fill the $r$-th position. The number of remaining objects for the $r$-th position is $n - (r-1) = n - r + 1$. So there are $n-r+1$ ways to fill the $r$-th slot.

By the Fundamental Principle of Counting (Multiplication Principle), the total number of ways to fill these $r$ ordered positions is the product of the number of choices for each position:

$$ P(n, r) = n \times (n-1) \times (n-2) \times \ldots \times (n-r+1) $$

This product consists of $r$ terms. We can express this product using factorial notation. Recall that $n! = n \times (n-1) \times \ldots \times (n-r+1) \times (n-r) \times \ldots \times 1$. The terms from $(n-r)$ down to 1 are not included in our product for $P(n,r)$. We can divide $n!$ by $(n-r)!$ to cancel out these terms:

$$ P(n, r) = n \times (n-1) \times \ldots \times (n-r+1) $$ $$ P(n, r) = \frac{n \times (n-1) \times \ldots \times (n-r+1) \times (n-r) \times (n-r-1) \times \ldots \times 1}{(n-r) \times (n-r-1) \times \ldots \times 1} $$

The numerator is $n!$, and the denominator is $(n-r)!$.

So, the formula for the number of permutations of $n$ distinct objects taken $r$ at a time is:

A special case is when $r=n$, which means we are arranging all $n$ distinct objects. The number of permutations of $n$ distinct objects taken $n$ at a time is:

$$ P(n, n) = \frac{n!}{(n-n)!} = \frac{n!}{0!} $$

By the convention that $0! = 1$:

$$ P(n, n) = \frac{n!}{1} = n! $$

So, the number of ways to arrange $n$ distinct objects in a line is $n!$.

Examples with Distinct Objects

Answer:

---

Answer:

---

Permutations with Identical Objects

When we need to find the number of distinct permutations of a set of objects where some of the objects are identical, the standard formula $\frac{n!}{(n-r)!}$ (or $n!$ if arranging all) cannot be used directly because swapping two identical objects does not create a new, distinct arrangement.

Consider a set of $n$ objects in total. Suppose these $n$ objects consist of $k$ different types of objects, where:

• There are $n_1$ identical objects of the first type.
• There are $n_2$ identical objects of the second type.
• ...
• There are $n_k$ identical objects of the $k$-th type.

And the total number of objects is the sum of the counts of each type: $n_1 + n_2 + \ldots + n_k = n$.

The number of distinct permutations of these $n$ objects (taken all at once) is given by the formula:

Rationale: If all $n$ objects were distinct, there would be $n!$ permutations. However, because there are $n_1$ identical objects of type 1, their $n_1!$ permutations among themselves in any arrangement are indistinguishable. We must divide by $n_1!$ to correct for this overcounting. Similarly, we divide by $n_2!$ for the identical objects of type 2, and so on, up to $n_k!$.

Example

Answer:

Permutations are used in a wide range of problems where the order of selection or arrangement is critical, such as creating passwords, ranking items, scheduling events, or forming words from letters. The distinction between distinct and identical objects is crucial for applying the correct formula.

Combinations: Definition, Formula, and Important Results

Selections of Objects

In contrast to permutations, where the order of arrangement is crucial, a combination is a way of selecting objects from a set where the order of selection does not matter. We are interested in the group or subset of objects chosen, not the sequence in which they were picked.

For example, if we are choosing two students from a group of five to form a committee, selecting Student A then Student B results in the same committee as selecting Student B then Student A. Since the order doesn't change the resulting group, this is a combination problem.

---

Definition of Combination

A combination is formally defined as a selection of objects from a set where the order of selection is irrelevant. We are interested in the number of distinct subsets of a certain size that can be formed from a larger set of distinct objects.

The number of combinations of $n$ distinct objects taken $r$ at a time is the number of ways to choose a subset of $r$ objects from a set of $n$ distinct objects, without considering the order in which the objects are chosen. This is denoted by $C(n, r)$, $_nC_r$, $\binom{n}{r}$, or sometimes $C_r^n$.

The parameters $n$ and $r$ are non-negative integers, with $0 \le r \le n$. We are choosing a subset of size $r$ from a set of $n$ distinct items.

---

Formula for Combinations of Distinct Objects

The formula for calculating the number of combinations can be derived directly from the formula for permutations. Recall that a permutation of $n$ distinct objects taken $r$ at a time ($P(n, r)$) involves two successive steps:

1. First, choosing $r$ objects from the $n$ distinct objects. The number of ways to do this is the definition of $C(n, r)$.
2. Second, arranging these $r$ chosen objects in a specific order. The number of ways to arrange $r$ distinct objects is $r!$.

By the Fundamental Principle of Counting (Multiplication Principle), the total number of permutations of $n$ objects taken $r$ at a time is the product of the number of ways for these two steps:

$$ P(n, r) = C(n, r) \times r! $$

Now, we can rearrange this equation to find the formula for $C(n, r)$ by dividing both sides by $r!$ (assuming $r! \neq 0$, which is true since $r \ge 0$):

$$ C(n, r) = \frac{P(n, r)}{r!} $$

We already know the formula for permutations of distinct objects: $P(n, r) = \frac{n!}{(n-r)!}$. Substitute this formula into the expression for $C(n, r)$:

$$ C(n, r) = \frac{\frac{n!}{(n-r)!}}{r!} $$

Dividing by $r!$ is the same as multiplying by $\frac{1}{r!}$:

$$ C(n, r) = \frac{n!}{(n-r)!} \times \frac{1}{r!} $$ $$ C(n, r) = \frac{n!}{r!(n-r)!} $$

The formula for the number of combinations of $n$ distinct objects taken $r$ at a time ($0 \le r \le n$) is:

This formula is read as "n choose r".

Let's examine some special cases:

• $C(n, 0)$: The number of ways to choose 0 objects from a set of $n$ distinct objects. $$ C(n, 0) = \frac{n!}{0!(n-0)!} = \frac{n!}{1 \times n!} = \frac{n!}{n!} = 1 $$ There is only one way to choose nothing from a set.
• $C(n, n)$: The number of ways to choose all $n$ objects from a set of $n$ distinct objects. $$ C(n, n) = \frac{n!}{n!(n-n)!} = \frac{n!}{n!0!} = \frac{n!}{n! \times 1} = \frac{n!}{n!} = 1 $$ There is only one way to choose everything from a set.

Examples with Distinct Objects

Answer:

---

Answer:

---

Important Results and Properties of Combinations

The combination formula $\binom{n}{r}$ has several useful properties:

1. Symmetry Property: $C(n, r) = C(n, n-r)$.

   The number of ways to choose a group of $r$ objects from $n$ is equal to the number of ways to choose the group of $n-r$ objects that are left behind.

   Proof: Using the formula for $C(n, r)$, let's calculate $C(n, n-r)$:

   $$ C(n, n-r) = \frac{n!}{(n-r)!(n-(n-r))!} $$ $$ = \frac{n!}{(n-r)!(n-n+r)!} $$ $$ = \frac{n!}{(n-r)!r!} $$

   Since multiplication is commutative ($r!(n-r)! = (n-r)!r!$), this is the same as $C(n, r)$.

   $$ C(n, n-r) = C(n, r) $$

   Example: $C(5, 2) = 10$. $C(5, 5-2) = C(5, 3) = \frac{5!}{3!2!} = \frac{120}{6 \times 2} = 10$. The property holds.

2. $C(n, 0) = 1$ and $C(n, n) = 1$. (As derived earlier).
3. $C(n, 1) = n$. The number of ways to choose 1 object from a set of $n$ is simply $n$.

   Proof: $C(n, 1) = \frac{n!}{1!(n-1)!} = \frac{n \times (n-1)!}{1 \times (n-1)!} = n$.

4. Pascal's Identity: $C(n, r) + C(n, r-1) = C(n+1, r)$.

   This identity shows how the numbers in Pascal's triangle are generated. It states that the number of ways to choose $r$ items from $n+1$ items is the sum of the number of ways to choose $r$ items from $n$ items (excluding one specific item) and the number of ways to choose $r-1$ items from $n$ items (which means including that one specific item and choosing $r-1$ more from the remaining $n$).

   Proof: This can be proven using the factorial formula, but it's algebraically more involved than the symmetry proof.

5. Sum of Combinations: The sum of all possible combinations from choosing 0 items up to choosing $n$ items from a set of $n$ elements is equal to $2^n$.

   $$ \sum_{r=0}^n C(n, r) = C(n, 0) + C(n, 1) + C(n, 2) + \ldots + C(n, n) = 2^n $$

   This is equal to the total number of subsets (including the empty set and the set itself) that can be formed from a set containing $n$ distinct elements.

   Connection to Binomial Theorem: This result is also obtained from the Binomial Theorem, which states that $(x+y)^n = \sum_{r=0}^n \binom{n}{r} x^{n-r} y^r$. Setting $x=1$ and $y=1$, we get $(1+1)^n = \sum_{r=0}^n \binom{n}{r} (1)^{n-r} (1)^r$, which simplifies to $2^n = \sum_{r=0}^n \binom{n}{r}$.

Combinations are widely used in scenarios where the formation of groups or subsets is involved and the order of selection does not impact the outcome, such as selecting teams, choosing lottery numbers, determining probabilities in card games, or selecting ingredients for a recipe.

Applications of Permutations and Combinations (Division into Groups, Distribution)

Permutations and combinations are fundamental concepts in combinatorics and probability theory. They provide systematic methods for counting the number of ways to arrange or select objects, which is essential for solving problems in various fields, including statistics, computer science, finance, and science.

Permutations are used when the order of objects matters, while combinations are used when the order does not matter. Let's explore some common applications of these concepts.

---

Applications of Permutations

Permutations are applied in situations where the sequence or the specific order of the chosen objects is important. The key question is "How many ways to arrange/order $r$ items out of $n$?"

Common Applications of Permutations:

1. Arrangement of Objects in a Line or Specific Positions: Counting the number of distinct ways to arrange a set of distinct objects, or a subset of objects, in a linear order or into designated positions.

   Example: How many ways can 5 distinct books be arranged on a shelf? This is arranging all 5 distinct items: $P(5, 5) = 5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$ ways.

   Example: How many ways can the top 3 finishers be determined in a race with 8 participants? This is selecting 3 participants out of 8 and ordering them for 1st, 2nd, and 3rd place: $P(8, 3) = \frac{8!}{(8-3)!} = \frac{8!}{5!} = 8 \times 7 \times 6 = 336$ ways.

2. Forming Numbers or Words from Digits or Letters: Counting the number of distinct numbers that can be formed using a set of digits, where the order of the digits creates a different number (e.g., 123 is distinct from 321). Similarly, counting the number of distinct "words" or arrangements of letters from a given set of letters.

   Example: How many different 3-digit numbers can be formed using the digits 1, 2, 3, 4 if no digit is repeated? This is arranging 3 out of 4 distinct digits: $P(4, 3) = \frac{4!}{(4-3)!} = \frac{4!}{1!} = 24$ ways.

3. Sequencing Tasks or Events: Counting the number of possible orders in which a series of tasks or events can be performed.

   Example: A manager needs to assign 5 different tasks to 5 different employees. In how many different orders can the tasks be assigned? This is arranging 5 distinct tasks: $P(5, 5) = 5! = 120$ ways.

4. Ranking or Ordering: Counting outcomes where the specific rank or position of each item is important.

Example Application of Permutation

Answer:

---

Applications of Combinations

Combinations are applied in situations where we are selecting a group or a subset of objects, and the order in which the objects are selected does not matter. The key question is "How many ways to choose/select $r$ items out of $n$?"

Common Applications of Combinations:

1. Formation of Committees or Teams: Counting the number of ways to select a group of people for a committee, a team, or any other group where positions are not distinct.

   Example: Choosing a committee of 4 members from a group of 10 people. The order of selection doesn't matter: $C(10, 4) = \frac{10!}{4!6!} = \frac{10 \times 9 \times 8 \times 7}{4 \times 3 \times 2 \times 1} = 10 \times 3 \times 7 = 210$ ways.

2. Selection of Items from a Collection: Counting the number of ways to choose a certain number of items from a larger collection without regard to the order.

   Example: Selecting 3 books to read from a list of 7 books. The order you pick them doesn't matter for which books you end up with: $C(7, 3) = \frac{7!}{3!4!} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35$ ways.

3. Forming Subsets: Counting the number of subsets of a given size from a set. The definition of $C(n, r)$ is precisely the number of subsets of size $r$ from a set of $n$ elements.
4. Card Games: Calculating the number of possible hands in card games, as the order in which you receive cards does not matter for the composition of your hand.

   Example: Number of possible 5-card poker hands from a standard deck of 52 cards: $C(52, 5) = \frac{52!}{5!47!} = 2,598,960$ ways.

5. Geometry Problems: Counting the number of lines, triangles, squares, etc., that can be formed by selecting points from a given set of points.

   Example: How many distinct lines can be drawn through 7 points, no three of which are collinear? To form a line, you need to choose 2 points. The order doesn't matter: $C(7, 2) = \frac{7!}{2!5!} = \frac{7 \times 6}{2 \times 1} = 21$ lines.

Example Application of Combination

Answer:

---

Applications involving Division into Groups or Distribution

A specific category of counting problems involves dividing a set of distinct items into groups of predetermined sizes, or distributing distinct items among distinct recipients. These problems often require the use of combinations.

Example: Dividing $n$ distinct items into two groups of sizes $r$ and $n-r$.

Suppose you have $n$ distinct items and want to divide them into two groups, one of size $r$ and the other of size $n-r$.

• First, choose $r$ items for the first group from the $n$ items. The number of ways to do this is $C(n, r)$.
• The remaining $n-r$ items automatically form the second group. There is only $C(n-r, n-r) = 1$ way to choose these remaining items.

So, the number of ways to divide $n$ distinct items into two groups of size $r$ and $n-r$ is $C(n, r) \times C(n-r, n-r) = C(n, r) \times 1 = C(n, r) = \frac{n!}{r!(n-r)!}$.

However, there's a subtlety: does the order of the groups matter? For instance, is dividing into Group A (size $r$) and Group B (size $n-r$) different from dividing into Group B (size $n-r$) and Group A (size $r$)?

• If the groups are distinguishable (e.g., giving one group to Person 1 and the other to Person 2, or forming a "left pile" and a "right pile" where the piles are different by position), then the number of ways is indeed $C(n, r)$.
• If the groups are indistinguishable (e.g., simply dividing into two piles of size $r$ and $n-r$ without assigning them to specific locations or people), and the group sizes are the same ($r = n-r = n/2$), then the two groups are interchangeable. We have counted every division twice (once as {Group1, Group2} and once as {Group2, Group1}). In this case, we must divide the result by $2!$ to correct for this double counting. The number of ways is $\frac{C(n, n/2)}{2!}$. If the group sizes are different ($r \neq n-r$), the groups are inherently distinguishable by their size, and we don't divide by $2!$.

Example

Answer:

Understanding when to use permutations (order matters) versus combinations (order doesn't matter) and how to handle situations involving identical objects or group divisions is key to successfully solving a wide range of counting problems.